import time
import json


def lagrange_interpolation(x: list, y: list, xi: float):
    n = len(x)

    def lagrange(i, j):
        if i == j:
            return y[i]
        else:
            v = 1
            for k in range(n):
                if k != i and k != j:
                    v *= (xi - x[k]) / (x[i] - x[k])
            return v

    def interpolation(xi):
        s = 0
        for i in range(n):
            s += lagrange(i, xi)
        return s

    return interpolation(xi)


def handle(req):
    st = time.time()
    """handle a request to the function
    Args:
        req (str): request body
    """
    jsonObj = json.loads(req)
    x = jsonObj["x"]
    y = jsonObj["y"]
    xi = jsonObj["xi"]
    res = lagrange_interpolation(x, y, xi)

    et = time.time()
    return (et - st) * 1000


if __name__ == "__main__":
    data = {
        "x": [1, 2, 3, 4, 5],
        "y": [2, 3, 4, 5, 6],
        "xi": 1.5
    }
    res = handle(json.dumps(data))
    print(type(res))
    print(res)
